package src;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.List;
import java.util.Vector;

import org.apache.lucene.index.CorruptIndexException;
import org.apache.lucene.index.IndexReader;
import org.apache.lucene.search.IndexSearcher;

//import lib.WordNet.WordNet;



public class LCS {

	/**
	 * @param args
	 */
//	 These are "constants" which indicate a direction in the backtracking array.
	private static final int NEITHER     = 0;
	private static final int UP          = 1;
	private static final int LEFT        = 2;
	private static final int UP_AND_LEFT = 3;

	private static double factor = 3;
	private static double threshold = 1/factor;
	
	private static double globalThreshold = 0.5; //threshold for hindi word to be added into list
	public static String LCSAlgorithm(String a, String b) {
		int n = a.length();
		int m = b.length();
		int S[][] = new int[n+1][m+1];
		int R[][] = new int[n+1][m+1];
		int ii, jj;

		// It is important to use <=, not <.  The next two for-loops are initialization
		for(ii = 0; ii <= n; ++ii) {
			S[ii][0] = 0;
			R[ii][0] = UP;
		}
		for(jj = 0; jj <= m; ++jj) {
			S[0][jj] = 0;
			R[0][jj] = LEFT;
		}

		// This is the main dynamic programming loop that computes the score and
		// backtracking arrays.
		for(ii = 1; ii <= n; ++ii) {
			for(jj = 1; jj <= m; ++jj) { 
	
				if( a.charAt(ii-1) == b.charAt(jj-1) ) {
					S[ii][jj] = S[ii-1][jj-1] + 1;
					R[ii][jj] = UP_AND_LEFT;
				}

				else {
					S[ii][jj] = S[ii-1][jj-1] + 0;
					R[ii][jj] = NEITHER;
				}

				if( S[ii-1][jj] >= S[ii][jj] ) {	
					S[ii][jj] = S[ii-1][jj];
					R[ii][jj] = UP;
				}

				if( S[ii][jj-1] >= S[ii][jj] ) {
					S[ii][jj] = S[ii][jj-1];
					R[ii][jj] = LEFT;
				}
			}
		}

		// The length of the longest substring is S[n][m]
		ii = n; 
		jj = m;
		int pos = S[ii][jj] - 1;
		char lcs[] = new char[ pos+1 ];

		// Trace the backtracking matrix.
		while( ii > 0 || jj > 0 ) {
			if( R[ii][jj] == UP_AND_LEFT ) {
				ii--;
				jj--;
				lcs[pos--] = a.charAt(ii);
			}
	
			else if( R[ii][jj] == UP ) {
				ii--;
			}
	
			else if( R[ii][jj] == LEFT ) {
				jj--;
			}
		}

		return new String(lcs);
	}
/*
	public static Vector getVariation(String token, Hashtable idfHash, int bitIndex, 
			Vector dictionary) throws FileNotFoundException, IOException{
		Vector candidates = new Vector();
		String candidateWord;		
		GetNewCluster gnc = new GetNewCluster();
		
		for (int i = 0; i < dictionary.size(); i++){
			candidateWord = (String)dictionary.get(i);
			String subSequence = LCSAlgorithm(token, candidateWord);
			int myEditDistance = gnc.SMSEditDistance(candidateWord, token);
			//&&(subSequence.length() > token.length() * threshold)
			if ((candidateWord.length() != 0)
					&&(token.toLowerCase().charAt(0) == candidateWord.toLowerCase().charAt(0))){
				
				Float f = (Float) idfHash.get(candidateWord);
				
				if (f != null) {
					Variation v = new Variation(token, candidateWord,
						subSequence.length(), myEditDistance, f);				
					
					if (v.weight > globalThreshold) {
						v.setVarBitIndex(bitIndex);					
						candidates.add(v);
					}
				}
			}
		}
		
		return candidates;
	}*/		
	
	public static Vector<Variation> getVariationDicMatrix(IDF idf, String token, Hashtable idfHash, 
			int bitIndex, Vector dictionary, TokenFetcher tf) throws 
			FileNotFoundException, IOException, Exception{
		
		token = token.toLowerCase();
		Vector<Variation> candidates = new Vector<Variation>();
		Vector dic = null;
		String candidateWord;
		GetNewCluster gnc = new GetNewCluster();
		//token = "faces";
		int dicIndex = GetDocs.getAlphabetIndex(token.toLowerCase().charAt(0));
		
		
		// assumption that 2gether etc are neglected
		if (dicIndex != -1) {
			dic = (Vector) dictionary.get(dicIndex);
			Debug.print(dicIndex);
			Debug.print(dic.size());
		} else {
			Debug.print("dicIndex -1");
			return candidates;
		}
		int totalEnglishVariation = 1;
		boolean dictHasToken=false;
		if(dic.contains(token)) {
			dictHasToken=true;
		}
		
		for (int i = 0; i < dic.size(); i++) {
			if(dictHasToken){
				candidateWord = token;
			} else{
				candidateWord = (String) dic.get(i).toString().toLowerCase();
			}
			
			String subSequence = LCSAlgorithm(token.toLowerCase(), candidateWord);			
			int myEditDistance = gnc.SMSEditDistance(candidateWord, token.toLowerCase());

			//
			if ((candidateWord.length() != 0)					
					&&(token.toLowerCase().charAt(0) == candidateWord.toLowerCase().charAt(0))
					&&(subSequence.length() > Math.max(candidateWord.length(), token.length()) * threshold)
					) {
				//&&(conditions(candidateWord,token))
				//System.out.println("candidateWord:: "+candidateWord+"");
				Debug.print("candidateWord:: "+candidateWord+"");	
				
				Vector<Variation> hindiList1 = LCS.getHindiWords(token, candidateWord, subSequence,
						bitIndex, myEditDistance, idfHash);
				//float idfScore = idf.getIDF(candidateWord);
				//Vector<Variation> normalizedHindiList = LCS.getNormalizedHindiList(hindiList1);
				Iterator it22 = hindiList1.iterator();
				
				while(it22.hasNext()){
					Variation v  = (Variation)it22.next();
			//		v.weight = v.weight*idfScore;
					candidates.add(v);
				}
				
								
				/*List suggest = WordNet.suggestWordNetSynonyms(candidateWord);
				if(!suggest.isEmpty()){
					Iterator it = suggest.iterator();
					while(it.hasNext()){
						String synonym = (String)it.next();
						Vector<Variation> hindiList = LCS.getHindiWords(token, synonym, 
								subSequence, bitIndex, myEditDistance, idfHash, tf);
						Iterator it2 = hindiList.iterator();
						boolean flag = true;
						while(it2.hasNext()){
							if(flag){
								totalEnglishVariation++;
								flag = false;
							}
							Variation v  = (Variation)it2.next();
							candidates.add(v);
						}
					}
				}*/
			
			}
			if(dictHasToken)
				break;
		}
		//System.exit(-1);
		if(candidates.isEmpty()){
			//System.out.println("Candidate List is empty for the token");
		}
		
		/*
		//**added to handle hindi words**
		Vector hindiSetMatrix = getHindiMatrix();
		Vector hindisyns = getHindiToEnglish(token, hindiSetMatrix, gnc, idfHash, bitIndex);
		for(int i = 0; i < hindisyns.size(); i++){
			Variation v = (Variation) hindisyns.get(i);
			candidates.add(v);
		}
*/
	
		Collections.sort(candidates, new Comparer());
		Vector<Variation> prunedCandidates = LCS.reweight(candidates, totalEnglishVariation);
		//For experiment 2: taking best match only
		Collections.sort(prunedCandidates, new Comparer());
		
//		Vector<Variation> prunedCandidates2 = new Vector<Variation>();
//		if(prunedCandidates.size() != 0){
//			prunedCandidates2.add(prunedCandidates.get(0));
//		}
		
		/*Iterator<Variation> it = prunedCandidates.iterator();
		while(it.hasNext()){
			Variation v = it.next();
			v.weight = v.weight/prunedCandidates.get(0).weight;
		}*/
		
		return prunedCandidates;
		//return candidates;
	}
	

	public static boolean conditions(String candidateWord, String token){
		candidateWord=candidateWord.toLowerCase();
		token=token.toLowerCase();
		candidateWord=candidateWord.replaceAll("a","");
		candidateWord=candidateWord.replaceAll("e","");
		candidateWord=candidateWord.replaceAll("i","");
		candidateWord=candidateWord.replaceAll("o","");
		candidateWord=candidateWord.replaceAll("u","");
		
		token=token.replaceAll("a","");
		token=token.replaceAll("e","");
		token=token.replaceAll("i","");
		token=token.replaceAll("o","");
		token=token.replaceAll("u","");
		if(token.length()<1 || candidateWord.length()<1)
			return false;
		if(candidateWord.charAt(0)==token.charAt(0) && candidateWord.charAt(candidateWord.length()-1)==token.charAt(token.length()-1))
				return true;
		else
			return false;
		
		
	}

	/*removes words with multiple occurence and multiply their weight by N*/
	public static Vector<Variation> reweight(Vector<Variation> candidates, int totalEnglishVariation){
		Iterator<Variation> it = candidates.iterator();
		Vector<Variation> prunedList = new Vector<Variation>();
		Vector<Integer> count = new Vector<Integer>();
		
		while(it.hasNext()){
			Variation v = (Variation)it.next();
			int index;
			
			if((index = exist(v, prunedList))!= -1){
				Integer i = (Integer)count.get(index);
				count.setElementAt(new Integer(i.intValue()+1), index);				
				//increment weight
			} else{
				prunedList.add(v);
				count.add(new Integer(1));
			}
		}
		it =  prunedList.iterator();
		int i = 0;
		
		while(it.hasNext()){
			Variation v = it.next();
			Integer x = count.get(i);
			v.setWeight((v.weight*x.intValue())/totalEnglishVariation);
			prunedList.setElementAt(v,i);
			i++;
		}				
		return prunedList;
	}
	
	public static int exist(Variation v, Vector<Variation> prunedList){
		Iterator<Variation> it  = prunedList.iterator();
		int index = 0;
		while(it.hasNext()){
			Variation v1 = it.next();
			if(v1.word.equals(v.word)){
				return index;
			}else{
				index++;
			}
		}		
		return -1;
	}
	
	public static Vector<Variation> getHindiWords(String token, String englishVariation, 
			String subSequence, int bitIndex, int myEditDistance, Hashtable idfHash)
			throws	Exception {
		
		Vector<Variation> candidates = new Vector<Variation>();
		//Vector<Variation> wordTranslations = new Vector();
		List<Token> hindiTokens = TokenFetcher.getTokenList2(englishVariation);
		
		
		if(hindiTokens != null){
			//hindiTokens = normalize(hindiTokens);
			Iterator it = hindiTokens.iterator();
			int num = 0;
			
			while((it.hasNext())&&(num < 3)){
				num++;
				Token temp = (Token)it.next();
				if(temp.probability > 0.1){
				Float idf = (Float) idfHash.get(temp.getWord());//this is the idf score,

				if ((idf != null)) {
					//f=new Float(1.0);
					idf = idf*temp.getScore();//serious bug below change to english token
					String hindiWord = temp.token;
					Variation v = new Variation(token, englishVariation,hindiWord,
							subSequence.length(), myEditDistance, idf);
					if (v.weight > globalThreshold) {
						/*if(v.weight > 10){
						Debug.printUTF("token:: "+v.token+" word:: "+v.word+" weight "
								+v.weight+" myEditDistance:: "+myEditDistance+" idf:: "+idf
								+" subsequenceLength:: "+subSequence.length()
								+"subsequence:: "+ subSequence+" variation:: "+englishVariation
								+" hindiWord:: "+temp.token+"\n");
						}*/
						v.setVarBitIndex(bitIndex);					
						candidates.add(v);
					}
				}	
				}
			}
		}		
		return candidates;
	}
	
	public static List<Token> normalize(List<Token> hindiTokens){
	
		Iterator it = hindiTokens.iterator();
		int i = 0;
		float maxProb = 1;
		while(it.hasNext()){
			Token t = (Token)it.next();
			if(i == 0){
				maxProb = t.probability;
				i++;
			}						
			t.normalizeWeight(maxProb);
		}
		
		//for(i = 0; i < Math.min(5, hindiTokens.size()); i++){
			//Token t = (Token)hindiTokens.get(i);
			//normalizedListOfHindiTokens.add(t);
		//}
		return (List<Token>)hindiTokens;
	}
	
	public static Vector getSynSetMatrix() throws FileNotFoundException, IOException{		
		String file = SMSConstant.synset;
		Vector <Vector> synSetMatrix = new Vector <Vector> ();
		BufferedReader reader = new BufferedReader(new FileReader(file));
		String sentence = null;
		
		while ((sentence = reader.readLine()) != null) {
			String [] words = sentence.split(",");
			Vector <String> var = new Vector <String> ();
			
			for(int k = 0; k < words.length; k++){
				var.add(words[k]);
			}
			synSetMatrix.add(var);		
		}
		reader.close();
		return synSetMatrix;
	}
	
	public static Vector getSynonym(String token, Vector synSetMatrix, GetNewCluster gnc, 
			Hashtable idfHash, int bitIndex){
		
		Vector <Variation> candidates = new Vector <Variation> ();
		
		for(int i = 0; i < synSetMatrix.size(); i++){
			Vector synSet = (Vector) synSetMatrix.get(i);
			for(int j = 0; j < synSet.size(); j++){
				String candidateWord = (String) synSet.get(j);
				String subSequence = LCSAlgorithm(token, candidateWord);
				int myEditDistance = gnc.SMSEditDistance(candidateWord, token);
				
				if ((candidateWord.length() != 0)
						&&(subSequence.length() > token.length() * threshold)
						&&(token.toLowerCase().charAt(0) == candidateWord.toLowerCase().charAt(0))){
					
					for(int k = 0; k < synSet.size(); k++){
						Float f = (Float) idfHash.get((String)synSet.get(k));
					
						if(f != null){
							Variation v = new Variation(token, (String)synSet.get(k),
									subSequence.length(), myEditDistance, f);				
							//System.out.println(v.word+"::::"+v.token);
							if(v.weight > globalThreshold){
								//System.out.println(v.word+"::::"+v.token);
								v.setVarBitIndex(bitIndex);					
								candidates.add(v);
							}
						}	
					}
				}
			}
		}
		return candidates;
	}
	
	public double getWeight(String token, String word, Hashtable idfHash){
		if(token.toLowerCase().charAt(0) != word.toLowerCase().charAt(0)){
			return -1;
		}
		GetNewCluster gnc = new GetNewCluster();
		String subSequence = LCSAlgorithm(token, word);
		int myEditDistance = gnc.SMSEditDistance(word, token);
		if ((word.length() != 0) && (subSequence.length() > token.length() * threshold)) {			
			Float f = (Float) idfHash.get(word);
			
			if (f != null) {
				Variation v = new Variation(token, word,
					subSequence.length(), myEditDistance, f);				
				return v.weight;
			}	
		}
		return -1;	
	}

	public Hashtable getIdfHash(File file){
		String sentence = null;
		Hashtable <String, Float> idfHash = new Hashtable <String, Float>();
		try {
			BufferedReader reader = new BufferedReader(new InputStreamReader(
					new FileInputStream(file), "UTF8"));
			//BufferedReader reader = new BufferedReader(new FileReader(file));
			while ((sentence = reader.readLine()) != null) {
				String [] idf = sentence.split("::");
				idf[0] = idf[0].trim();
				idf[1] = idf[1].trim();
				Float f = Float.valueOf(idf[1]);
				idfHash.put(idf[0], f);
			}
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		} catch (IOException e) {
			e.printStackTrace();
		}
		
		return idfHash;
	}

	public Vector getMatrix(String indexDir,String smsQuery, Hashtable ht,Vector dictionary, TokenFetcher tf){
		Vector <Vector> matrix = new Vector <Vector>();
		int bitIndex = 0;
		IndexReader reader = null;
		try {
			reader = IndexReader.open(indexDir);
		} catch (CorruptIndexException e1) {
			// TODO Auto-generated catch block
			e1.printStackTrace();
		} catch (IOException e1) {
			// TODO Auto-generated catch block
			e1.printStackTrace();
		}
		IndexSearcher searcher = new IndexSearcher(reader);
		IDF idf = new IDF(reader, searcher);
		String [] tokens = smsQuery.split("[ ]+");
		try {

			for(int i = 0; i < tokens.length; i++){
				if (tokens[i].length() > 1) {					
					tokens[i] = tokens[i].replace("4", "for");
					tokens[i] = tokens[i].replace("8", "ate");
					tokens[i] = tokens[i].replace("10", "ten");
					
					Vector<Variation> v = getVariationDicMatrix(idf, tokens[i], ht, bitIndex, dictionary, tf);									
					//Debug.printVector(v);
					if (!v.isEmpty()) {
						Collections.sort(v, new Comparer());
						matrix.add(v);
						bitIndex++;
					}else{
						System.out.println(tokens[i]+" Empty list");
					}
				}
			}
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		} catch (IOException e) {
			e.printStackTrace();
		} catch (Exception e) {
			e.printStackTrace();
		}
		return matrix;
	}
	
	/*For Hindi to English Case*/
	public static Vector getHindiMatrix() throws FileNotFoundException, IOException{
		String file = SMSConstant.hindiToEnglish;
		Vector <Vector> hindiMatrix = new Vector <Vector> ();
		BufferedReader reader = new BufferedReader(new FileReader(file));
		String sentence = null;
		while ((sentence = reader.readLine()) != null) {
			String [] words = sentence.split(",");
			Vector <String> var = new Vector <String> ();
			for(int k = 0; k < words.length; k++){
				var.add(words[k]);
			}
			hindiMatrix.add(var);		
		}
		reader.close();
		return hindiMatrix;
	}
	
	/*For Hindi to English Case*/
	public static Vector getHindiToEnglish(String token, Vector hindiSetMatrix, GetNewCluster gnc, 
			Hashtable idfHash, int bitIndex){
		Vector <Variation> candidates = new Vector <Variation> ();
		
		for(int i = 0; i < hindiSetMatrix.size(); i++){
			Vector hindiToEnglishSet = (Vector) hindiSetMatrix.get(i);
			for(int j = 0; j < 1; j++){
				
				String candidateWord = (String) hindiToEnglishSet.get(j);				
				String subSequence = LCSAlgorithm(token, candidateWord);
				int myEditDistance = gnc.SMSEditDistance(candidateWord, token);
				
				if ((candidateWord.length() != 0)
						&&(subSequence.length() > token.length() * threshold)
						&&(token.toLowerCase().charAt(0) == candidateWord.toLowerCase().charAt(0))){
					
					for(int k = 1; k < hindiToEnglishSet.size(); k++){
						String word = (String) hindiToEnglishSet.get(k);
						String [] field = word.split(":");
						//System.out.println(field[0]+"  <----->  "+field[1]);
						String mycandidateWord = field[0];
						
						Float f = (Float) idfHash.get(mycandidateWord);
					
						if(f != null){
							
							Variation v = new Variation(token, field[0],
									subSequence.length(), myEditDistance, f);				
							//System.out.println(v.word+"::::"+v.token);
							Double prob = Double.valueOf(field[1]);
							v.setWeightWithProbability(prob);
							if(v.weight > 0.5){
								//System.out.println(v.word+"::::"+v.token);
								v.setVarBitIndex(bitIndex);					
								candidates.add(v);
							}
						}	
					}
				}
			}
		}
		return candidates;
	}
}
